import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-11-20
 * Time: 23:28
 */
public class Solution {
    public int n;
    public List<String> ans=new ArrayList<>();
    public StringBuilder stringBuilder=new StringBuilder();
    //left和right是已经放的左括号和右括号的数目
    public void dfs(int left,int right){
        if(stringBuilder.length()==2*n){
            this.ans.add(stringBuilder.toString());
            return ;
        }
        //先判断左括号
        if(left<n){

            stringBuilder.append("(");
            dfs(left+1,right);
            //左括号添加并递归完记得删除
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
        }
        if(left>right){
            stringBuilder.append(")");
            dfs(left,right+1);
            //右括号添加并递归完记得删除
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
        }
    }
    public List<String> generateParenthesis(int n) {
        this.n=n;
        dfs(0,0);
        return this.ans;
    }
}
